package exercise02;

import java.util.ArrayList;

public class Day230704 {
    // 盛最多水的容器

    // 时间复杂度: O(n)
    public int maxArea3(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left != right) {
            int minHeight = Math.min(height[left], height[right]);
            int tmp = (right - left) * minHeight;
            max = Math.max(max, tmp);
            // 优化版本
            // 一样的, 比较小的向内移动, 如果移动了高度更小, 或者不变, 继续移动
            while (left != right && height[left] <= minHeight) {
                left++;
            }
            while (left != right && height[right] <= minHeight) {
                right--;
            }

        }
        return max;
    }

    // 时间复杂度: O(n)
    public int maxArea2(int[] height) {
        // 双指针
        // 先取左右两边
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left != right) {
            int tmp = (right - left) * Math.min(height[left], height[right]);
            max = Math.max(max, tmp);
            // 谁比较小, 谁就向内移动
            // 因为向内移动, 宽度一定减小, 高度取决于小的
            // 比较大的向内移动, 只会更小(1. 高度不变 2. 高度更小)
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }

    // 暴力枚举, 超时
    // 时间复杂度: O(n2)
    public int maxArea1(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int tmp = (j - i) * Math.min(height[i], height[j]);
                if (tmp > max) {
                    max = tmp;
                }
            }
        }
        return max;
    }

    // 快乐数
    public int bitSum(int n) {
        int sum = 0;
        while (n >  0) {
            sum += Math.pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
    public boolean isHappy3(int n) {
        int slow = n;
        int fast = bitSum(n);
        while (slow != fast) {
            // 快慢指针, slow 进行一次操作, fast 进行两次操作
            // 因为一定会有循环, 所以slow 和 fast 最终会相等
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow == 1;
    }

    public boolean isHappy2(int n) {
        // 存放过程中的数
        ArrayList<Integer> list = new ArrayList<>();
        while (n != 1) {
            if (list.contains(n)) {
                // 出现之前已经出现过的数, 说明这个数将进入死循环
                // 一定会有重复的数出现, 会出现循环
                return false;
            }
            list.add(n);
            int tmp = 0;
            while (n >  0) {
                tmp += Math.pow(n % 10, 2);
                n /= 10;
            }
            n = tmp;

        }
        return true;
    }

    public boolean isHappy1(int n) {
        while (n != 1 && n != 7) {
            if (n < 10)
                return false;
            int tmp = 0;
            while (n > 0) {
                tmp += Math.pow(n % 10, 2);
                n /= 10;
            }
            n = tmp;
        }
        return true;
    }
}
